class Solution {
private:
    int n;
public:
    bool check(long long low,vector<long long>& base,int r,int k){

        long long other=0;
        long long cnt=0;
        vector<long long> exp(n+1);
        for(int i=1;i<=n;++i){
            other-=exp[i-1];
            long long cur=base[i]+other;
            if(cur<low){
                exp[min(n,i+2*r)]+=low-cur;
                other+=low-cur;
                cnt+=low-cur;
            }
        }
        return cnt<=k;
    }
    long long getSum(int left,int right,vector<long long>& f){

        left=max(1,left);
        right=min(n,right);
        return f[right]-f[left-1];
    }
    long long maxPower(vector<int>& stations, int r, int k) {
        
        n=stations.size();
        long long maxn=0,minn=0;
        vector<long long> f(n+1),base(n+1);
        for(int i=0;i<n;++i){
            f[i+1]=f[i]+stations[i];
        }
        for(int i=1;i<=n;++i){
            base[i]=getSum(i-r,i+r,f);
            maxn=max(base[i],maxn);
        }
        long long left=0,right=maxn+k;
        while(left<right){
            long long mid=left+(right-left+1)/2;
            if(check(mid,base,r,k)){
                left=mid;
            }
            else{
                right=mid-1;
            }
        }
        return left;
    }
};
